package com.gwcloud.leetcode.offers;

import java.util.LinkedList;
import java.util.List;

import com.gwcloud.leetcode.common.datastructure.TreeNode;

/** 
* @ClassName   : Leetcode0340 
* @author      : ganwei 
* @date        : 2020年6月4日 
* @Description : TODO 
*/
public class Leetcode0340 {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>(); 

	/**
     * -解题思路，遍历树,回溯全部路径
     */
	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		backtrace(root, sum);
        return res;
    }
	
	public void backtrace(TreeNode root, int sum) {
		if(root == null) {
			return;
		}
		
		path.add(root.val);
		sum -= root.val;
		if(sum == 0 && root.left == null && root.right == null) {
			res.add(new LinkedList<Integer>(path));
		}
		
		backtrace(root.left, sum);
		backtrace(root.right, sum);
		
		path.removeLast();
	}
	
	/**
	 * -主函数
	 */
	public static void main(String[] args) {
		
	}
	
}
